package 链表;

public class No147对链表进行插入排序 {

    /**
     * 示例 1：
     * 输入: 4->2->1->3
     * 输出: 1->2->3->4
     * 示例 2：
     * 输入: -1->5->3->4->0
     * 输出: -1->0->3->4->5
     * 就是对一个链表进行排序
     */

    public static ListNode insertionSortList(ListNode head) {

        if(head==null||head.next==null)
            return head;

        ListNode listNode=new ListNode();//用来存排序的节点

        ListNode pre=listNode;//前驱节点
        ListNode cur=head;//第一个比较的节点

        while (cur!=null){
            /**
             * 都与listNode一个个比较然后拼接到listNode后面
             */

            //从一开始的节点去比较
            while (pre.next!=null&&pre.next.val<cur.val){
                //从排序节点的第一个节点去比较
                pre=pre.next;
            }
            //出来就是在 小 和 大  中间

            ListNode dump=cur.next;//保存当前节点的下一个节点
            ListNode next= pre.next;//记录插入前节点的下一个节点
            pre.next=cur;//插入节点下一个节点为当前节点
            cur.next=next;//当前节点的下一个节点为先前记录的节点
            cur=dump;//变成下一个节点
            pre=listNode;//让前驱节点重置
        }
        return pre.next;
    }

    public static ListNode insertionSortListGood(ListNode head) {

        ListNode dummy = new ListNode(0);

        ListNode pre = dummy;//前驱节点

        ListNode cur = head;//第一个节点

        while (cur != null) {

            ListNode tmp = cur.next;//当前节点的下一位

            //前驱节点的下一位不会空,前驱节点的下一位的val小于当前val
            while (pre.next != null && pre.next.val < cur.val) {
                pre = pre.next;
            }
            //插进去

            cur.next = pre.next;

            pre.next = cur;

            pre = dummy;

            cur = tmp;

        }

        return dummy.next;
    }

    public static void main(String[] args) {
        int[] arr=new int[]{4,2,1,3};
        ListNode listNode = ListNode.createListNode(arr);
        ListNode result = insertionSortList(listNode);
        ListNode.printListNode(result);
    }

}
